#include <stdio.h>
#include <stdlib.h>

#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
#define LISTINCREMENT 10    //线性表存储空间的分配增量
#define ElemType int    //线性表元素类型定义
#define OK 1    //操作成功
#define ERROR 0 //操作失败

typedef struct
{
    ElemType *elem; //存储空间基址
    int length; //线性表当前长度
    int listsize;   //线性表当前分配的存储容量
} SqList;

int InitList_Sq(SqList *L)  //构造一个空的线性表L
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));//为线性表分配初始存储空间
    if (L->elem == NULL)    //存储分配失败
    {
        return ERROR;   //返回失败标志
    }
    L->length = 0;  //空表长度为0
    L->listsize = LIST_INIT_SIZE;   //初始存储容量
    return OK;  //返回成功标志
}

/* 在位置 i (1-based) 插入元素 e */
int ListInsert(SqList *L, int i, ElemType e)
{
    if (L == NULL) return ERROR;
    if (i < 1 || i > L->length + 1) return ERROR; /* 检查插入位置合法性 */

    /* 若当前存储空间已满，则增加分配 */
    if (L->length >= L->listsize) {
        ElemType *newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
        if (newbase == NULL) return ERROR;
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    }

    /* 将插入位置及之后元素后移一位（使用下标，避免指针边界问题） */
    for (int k = L->length - 1; k >= i - 1; --k) {
        L->elem[k + 1] = L->elem[k];
    }

    L->elem[i - 1] = e; /* 在位置 i-1 存放新元素 */
    L->length++;
    return OK;
}

/* 打印顺序表内容（元素索引从 1 开始显示） */
void PrintList(const SqList *L)
{
    if (L == NULL) return;
    printf("SqList length=%d, listsize=%d\n", L->length, L->listsize);
    for (int i = 0; i < L->length; ++i) {
        printf("L[%d]=%d\n", i + 1, L->elem[i]);
    }
}

/* 释放顺序表占用的存储 */
void DestroyList(SqList *L)
{
    if (L == NULL) return;
    if (L->elem != NULL) free(L->elem);
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
}

/* 在位置 i (1-based) 删除元素，并通过 e 返回被删除的元素 */
int ListDelete(SqList *L, int i, ElemType *e)
{
    if (L == NULL || e == NULL) return ERROR;
    if (i < 1 || i > L->length) return ERROR;

    *e = L->elem[i - 1];
    for (int k = i; k < L->length; ++k) {
        L->elem[k - 1] = L->elem[k];
    }
    L->length--;
    return OK;
}

/* 在顺序表中查找值为 val 的元素，返回其位置（1-based），找不到返回 0 */
int LocateElem(const SqList *L, ElemType val)
{
    if (L == NULL || L->elem == NULL) return 0;
    for (int i = 0; i < L->length; ++i) {
        if (L->elem[i] == val) return i + 1;
    }
    return 0;
}

/* 测试：初始化 [10,20,30,40,50]，删除值 20，然后打印 */
int main(void)
{
    SqList L;
    if (InitList_Sq(&L) == ERROR) {
        fprintf(stderr, "InitList_Sq failed\n");
        return 1;
    }

    /* 初始化为 10,20,30,40,50 */
    int initial[] = {10, 20, 30, 40, 50};
    int n = sizeof(initial) / sizeof(initial[0]);
    for (int i = 0; i < n; ++i) {
        /* 插入到表尾 */
        if (ListInsert(&L, L.length + 1, initial[i]) != OK) {
            fprintf(stderr, "ListInsert failed at index %d\n", i);
            DestroyList(&L);
            return 1;
        }
    }

    printf("初始顺序表：\n");
    PrintList(&L);

    /* 删除值为 20 的元素 */
    ElemType removed;
    int pos = LocateElem(&L, 20);
    if (pos == 0) {
        printf("未找到值 20，无法删除。\n");
    } else {
        if (ListDelete(&L, pos, &removed) == OK) {
            printf("已删除元素：%d（原位置 %d）\n", removed, pos);
            printf("删除后顺序表：\n");
            PrintList(&L);
        } else {
            printf("删除失败\n");
        }
    }

    DestroyList(&L);
    return 0;
}
